#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=214 lang=cpp
 *
 * [214] 最短回文串
 */

// @lc code=start
class Solution {
public:
    // 0-n回文串
    string shortestPalindrome(string s) {
        int end = -1;
        if (s.size() < 1) return s;
        for (int i = s.size(); i >= 1; i--) {
            string x = s.substr(0, i);
            if (isPalindrome(x)) {
                end = i; break;
            }
        }
        if (end == s.size()) return s;
        string add = s.substr(end);
        reverse(add.begin(), add.end());
        return add + s;

    }

    bool isPalindrome(const string & x) {
        int i = 0, j = x.size() - 1;
        while (i < j) {
            if (x[i] != x[j]) return false;
            i++; j--;
        }
        return true;
    }

    // KMP算法
};
// @lc code=end

